package leetcode.editor.cn;
//[1143]最长公共子序列
public class LongestCommonSubsequence1143{
public static void main(String[] args) {
   Solution solution = new LongestCommonSubsequence1143().new Solution();
   
}

  //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    //复习 one times  执行耗时:10 ms,击败了64.68% 的Java用户

    public int longestCommonSubsequence(String text1, String text2) {
        if (text1 == null || text1.length() < 1 || text2 == null || text2.length() < 1)return 0;
        //定义状态 m,n ,前 dp[i][j], index 的最大子序列。
        // dp[m][n] =
        //if (t1[m-1] == t2[n-1])
        //      -> dp[m-1][n-1]+1
        // else
        //      -> Max( dp[m-1][n],dp[m][n-1] )

        int a = text1.length();
        int b = text2.length();
        int res[][] = new int[a+1][b+1];
        //初始值 0 dp[0][0...j]=0; dp[0...i][0]=0; //默认都是0

        //index start 1 end len.  end dp[mlen][nlen]
        //not start 0 end len - 1. because .init value is 0. dp[0][0...j]=0; dp[0...i][0]=0;
        for (int i = 1; i <= a; i++) {
            for (int j = 1; j <= b; j++) {
                char ac = text1.charAt(i - 1);
                char bc = text2.charAt(j - 1);
                if (ac == bc){
                    res[i][j] = res[i-1][j-1] + 1;//开始位置 1 预留出所有的 初始值都是 0 。
                }else {
                    res[i][j] = Math.max(res[i-1][j],res[i][j-1]);
                }
            }
        }
        return res[a][b];
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}